//给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链
//表节点，返回 反转后的链表 。
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], left = 2, right = 4
//输出：[1,4,3,2,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [5], left = 1, right = 1
//输出：[5]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目为 n 
// 1 <= n <= 500 
// -500 <= Node.val <= 500 
// 1 <= left <= right <= n 
// 
//
// 
//
// 进阶： 你可以使用一趟扫描完成反转吗？ 
// Related Topics 链表 👍 1357 👎 0


package com.cjl.leetcode.editor.cn;

/**
 * [P92]_反转链表 II
 *
 * @author cjl
 * @date 2022-07-28 21:22:13
 */
public class P92_ReverseLinkedListIi {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P92_ReverseLinkedListIi().new Solution();
    }
    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        /**
         * 跑到当前待调换开始位置
         *
         * @param head
         * @param left
         * @param right
         * @return
         */
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode yNode = new ListNode();
            yNode.next = head;
            ListNode pre = yNode;

            for(int i = 1; i < left ; i++){
                pre = pre.next;
            }
            ListNode currNode = pre.next;
            ListNode nextNode = currNode.next;
            for(int i =left ; i < right; i++){
                currNode.next = nextNode.next;
                nextNode.next = pre.next; //开始交换待头节点
                pre.next = nextNode;
                //当前节点不变，但是next节点会变化
                nextNode = currNode.next;
            }
            return yNode.next;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}